Bağlantılama ile çatışmanın kotarılması

11.4.2. Çırpı Fonksiyonda Çatışmaların Önlenmesi

Uygulamada, çoğu zaman, ideal çırpı fonksiyonu bulmak zordur ve hatta imkansız olan durumlar da olabilir. Bu durumunda çırpı algoritması çatışma olacak şekilde kotarılır. Çatışma bir veya daha çok ayrık giriş değerinin aynı tamsayıyı üretmesidir. Böyle durumlarda, biri açık adresleme (open addressing) diğeri bağlantılama (linking) olarak adlandırılan iki temel yaklaşımdan birisi kullanılır:

    • Açık Adresleme (Open Addressing)
      Bu yaklaşım şeklinde, eğer çırpı fonksiyonu halıhazırda kullanılan bir satıra ait indis üretirse, kendisinden sonra gelen, yani açık olan bir indis üretir. Böylece çatışmaya neden olan sonuç yeniden çırpılanarak boş bir göze kaydırılmış olunur.
    • Bağlantılama (Linking)
      Bağlantılamada, bağlantılı listelerden veya ağaç veri modellerinden yararlanılır. Çatışma sonucu aynı indise sahip ayrık veriler birbirine Şekilde görüldüğü gibi bağlantılı liste veya ikili ağaç şeklinde bağlanırlar. Dolayısıyla, çırpı fonksiyonu üzerinden indis bulunduktan sonra bağlantılı liste veya ikili ağaç üzerinde arama yapılması için dolaşılması gerekir.